/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/maximal-rectangle
   @Language: C++
   @Datetime: 19-04-10 14:24
   */

class Solution {
	int largestRectangleArea(vector<int> &height) {
		if (height.size()<1) return 0;
		stack<int> pos;
		int mx = 0;
		for (int i=0; i<=height.size();){
			if(pos.size()<1 || (i<height.size() && height[pos.top()]<height[i]))
				pos.push(i++);		// record current max number pos
			else{
				int h = height[pos.top()];
				pos.pop();
				if (pos.size()) mx = max(mx,(i-pos.top()-1)*h);
				else mx = max(mx, i*h);
			}
		}
		return mx;
	}
public:
	/**
	 * @param matrix: a boolean 2D matrix
	 * @return: an integer
	 * Tip: accmulate each colomn as its height
	 *      see problem 122 largest-rectangle-in-histogram
	 */
	int maximalRectangle(vector<vector<bool>> &matrix) {
		// write your code here
		if(matrix.size()<1 || matrix[0].size()<1) return 0;
		int m=matrix.size(), n=matrix[0].size(), area=0;
		vector<int> height(n,0);
		for(const auto &row:matrix){
			for(int i=0; i<n; ++i)
				height[i]=row[i]?height[i]+1:0;
			area=max(area,largestRectangleArea(height));
		}
		return area;
	}
};
